
package com.liwt.pongo;

/**
 * 倒水问题：（来自庞果网）
 * <p>
 * 有两个容器，容积分别为A升和B升，有无限多的水，现在需要C升水。
 * <p>
 * 我们还有一个足够大的水缸，足够容纳C升水。起初它是空的，我们只能往水缸里倒入水，而不能倒出。
 * <p>
 * 可以进行的操作是：
 * <p>
 * 1,把一个容器灌满；
 * <p>
 * 2,把一个容器清空（容器里剩余的水全部倒掉，或者倒入水缸）；
 * <p>
 * 3,用一个容器的水倒入另外一个容器，直到倒出水的容器空或者倒入水的容器满。
 * <P>
 * 问是否能够通过有限次操作，使得水缸最后恰好有C升水。
 * <p>
 * 输入：三个整数A, B, C，其中 0 < A , B, C <= 1000000000
 * <p>
 * 输出：true或false，表示能否达到要求。
 * 
 * @author likebamboo
 * @create 2013-10-18
 * @see http://www.cnblogs.com/dyllove98/archive/2013/07/24/3212578.html
 */
public class Water {

    /**
     * 求最大公约数
     * 
     * @param a
     * @param b
     * @return
     */
    private static int gcd(int a, int b) {
        int temp;
        if (a < b) {/* 交换两个数，使大数放在a上 */
            temp = a;
            a = b;
            b = temp;
        }
        while (b != 0) {/* 利用辗除法，直到b为0为止 */
            temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

    public static boolean can(int a, int b, int c) {
        int gcd = gcd(a, b);
        if (c % gcd == 0) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(can(4, 8, 46548));
    }
}
